package leetcode.code0924;

import java.util.Arrays;

public class Solution {

	int n;

	int[] p;// 并查集root
	int[] s;// 连通节点数量
	int[] m;// 感染节点数量
	int[] o;// 感染来源

	public int minMalwareSpread(int[][] graph, int[] initial) {
		// 初始化并查集
		n = graph.length;
		p = new int[n];
		s = new int[n];
		m = new int[n];
		o = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = i;
			s[i] = 1;
		}
		// 连通节点，记录连通节点数量
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (graph[i][j] == 1) {
					int pi = find(i), pj = find(j);
					if (pi == pj)
						continue;
					int si = s[pi], sj = s[pj];
					p[pi] = pj;
					s[pj] = si + sj;
				}
			}
		}
		// 每个连通块的感染数量
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < initial.length; i++) {
			int cur = find(initial[i]);
			m[cur]++;
			o[cur] = initial[i];
			min = Math.min(min, initial[i]);
		}
		int ansi = -1, anss = -1;
		// 只有感染数量是1的有救，这其中联通最大的最值得救，先出先算
		for (int i = 0; i < n; i++) {
			if (m[i] == 1) {
				if (s[i] > anss) {
					ansi = o[i];
					anss = s[i];
				} else if (s[i] == anss && o[i] < ansi) {
					ansi = o[i];// 感染源小的
				}
			}
		}
		return ansi == -1 ? min : ansi;
	}

	private int find(int index) {
		if (p[index] != index) {
			p[index] = find(p[index]);
		}
		return p[index];
	}

}
